/*
 * 二叉堆函数 用于从小到大排序 获取最小的值
 *
 * */
import { Node } from "./Node";

class MinBinaryHeap {
    /** key表示用来排序的字段 */
    key: string;
    /** 堆大小 这里堆大小和数组大小一致 */
    size: number;
    /** 用于存放堆元素 存放的是对象 */
    list: Node[] = [];

    constructor(key: string) {
        this.key = key; //key表示用来排序的字段
        this.size = 0; //堆大小 这里堆大小和数组大小一致
        this.list = []; //用于存放堆元素 存放的是对象
    }
    //获取某个节点的父节点
    parent(i: number) {
        let p = Math.floor((i - 1) / 2);
        if (i > this.size - 1 || p < 0) return null;
        return p; //这里返回的 p 是在数组中的下标，数组是从0开始的
    }
    //获取某个节点的左孩子
    left(i: number) {
        let l = 2 * i + 1;
        if (l > this.size - 1) return null;
        return l;
    }
    //获取某个节点的右孩子
    right(i: number) {
        let r = 2 * i + 2;
        if (r > this.size - 1) return null;
        return r;
    }
    minHeapify(i: number) {
        let list = this.list;
        let key = this.key;
        let l = this.left(i);
        let r = this.right(i);
        let smallest = null;
        if (l != null) {
            //左孩子为空则右孩子一定为空
            if (r == null) smallest = l;
            else smallest = list[l][key] < list[r][key] ? l : r;
            if (list[i][key] <= list[smallest][key]) return;
            else {
                let t = list[i];
                list[i] = list[smallest];
                list[smallest] = t;
                this.minHeapify(smallest);
            }
        }
    }
    //元素上浮 对下标为i的元素进行向上调整，使堆保持其性质
    increase(i: number) {
        let list = this.list;
        let p = this.parent(i);
        while (i > 0 && list[p][this.key] > list[i][this.key]) {
            //i > 0 一定能保证 p != null
            let t = list[i];
            list[i] = list[p];
            list[p] = t;
            i = this.parent(i);
            p = this.parent(i);
        }
    }
    //构建堆
    buildHeap(a: Node[]) {
        this.list = a;
        this.size = a.length;
        for (let i = Math.floor(a.length / 2) - 1; i > -1; i--) {
            this.minHeapify(i);
        }
    }
    //堆排序 由大到小
    heapSort(a: Node[]) {
        this.buildHeap(a);
        for (let i = this.size - 1; i > 0; i--) {
            let t = this.list[0];
            this.list[0] = this.list[i];
            this.list[i] = t;
            this.size--;
            this.minHeapify(0);
        }
        return this.list;
    }
}

export class MinPriorityQueue {
    minBinaryHeap: MinBinaryHeap;
    key: string;
    constructor(key: string, nodes: Node[]) {
        // if (!(this instanceof MinPriorityQueue)) return new MinPriorityQueue(key, a);
        this.minBinaryHeap = new MinBinaryHeap(key);
        this.minBinaryHeap.buildHeap(nodes);
        this.key = key;
    }

    /**
     * 添加一个元素
     * @param node
     */
    insert(node: Node) {
        this.minBinaryHeap.size++;
        this.minBinaryHeap.list[this.minBinaryHeap.size - 1] = node;
        //向上调整
        this.minBinaryHeap.increase(this.minBinaryHeap.size - 1);
    }

    /**
     * 获取最小的一个元素
     * @param remove 表示获取后是否删除 true 删除 false 不删除
     */
    min(remove: boolean) {
        //获取最小元素
        let min = this.minBinaryHeap.list[0];
        if (remove) this.removeMin();
        return min;
    }

    /** 删除最小的一个元素 */
    removeMin() {
        //移除最小元素
        let list = this.minBinaryHeap.list;
        let size = this.minBinaryHeap.size;
        let min = list[0];
        list[0] = list[size - 1];
        list.shift(); //删除
        this.minBinaryHeap.size--;
        this.minBinaryHeap.minHeapify(0);
        return min;
    }

    /**
     * 更新元素
     * @param i 更新的索引
     * @param node
     */
    update(i: number, node: Node) {
        this.minBinaryHeap.list[i] = node;
        this.minBinaryHeap.minHeapify(i);
        this.minBinaryHeap.increase(i);
    }
}
